package 题目集.树.构建树;

import org.junit.Test;

public class 完全二叉树前序转后序 {
    int[] preOrder;
    int[] postOrder;
    int cnt;

    public int[] fun(int[] preOrder) {
        postOrder = new int[preOrder.length];
        this.preOrder = preOrder;
        cnt = 0;
        build(0, preOrder.length - 1);
        return postOrder;
    }

    public void build(int s, int e) {
        if (s > e) return;
        postOrder[e] = preOrder[cnt++]; //  根节点映射
        int m = s + e >> 1;
        //这里给终点-1，是因为每次处理的都是终点，所以终点在下次递归中要变化
        build(s, m-1);  //先处理前序的左树
        build(m , e-1); //处理前序的右树
    }

    @Test
    public void test() {
        int[] preOrder = {4, 2, 1, 3, 6, 5, 7};
        int[] fun = fun(preOrder);
        for (int i : fun) {
            System.out.print(i + " ");
        }
    }
}
